package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author he peng
 * @create 2018/4/13 13:49
 * @see
 */
public class SortAlgorithmTest {

    @Test
    public void selectSort() throws Exception {
        // 选择排序算法
        int[] target = {1 , 3 , 22 , 43 , 3454 , -99 , 234 , 131 , 32 , 54};
        System.out.println("sort before ==> " + Arrays.toString(target));
        for (int i = 0 ;i < target.length; i++) {
            int max = target[i];
            for (int j = i + 1 ;j < target.length ; j++) {
                int currentCompareVal = target[j];
                if (max > currentCompareVal) {
                    continue;
                }
                // swap
                int newMax = currentCompareVal;
                target[j] = max;
                target[i] = newMax;
                max = newMax;
            }
        }
        System.out.println("sort after ==> " + Arrays.toString(target));

        // 选择排序算法是性能十分低的排序算法 , 时间开销与问题规模 N 无关 , 总是要进行 N * ( N - 1 ) 循环 + Swap 次数
    }

    @Test
    public void bubbleSort() throws Exception {
        // 冒泡排序算法
        int[] target = {1 , -7347 , 3 , 22 , 324 , 42212 , 43 , 3454 , -99 , 234 , 131 , 32 , 54};
        System.out.println("sort before ==> " + Arrays.toString(target));

        // 两两比较选出其中的较大或者较小值 , 每完成一次全比较后都会得到一个最大值，或者是最小值 （取决于升序或者降序排序）
        for (int i = 0;i < target.length; i++) {
            for (int j = 0 ;j < target.length - i - 1; j++) {
                int compareVal1 = target[j];
                int compareVal2 = target[j + 1];
                if (compareVal1 > compareVal2) {
                    continue;
                }
                // swap
                target[j] = compareVal2;
                target[j + 1] = compareVal1;
            }
        }
        System.out.println("sort after ==> " + Arrays.toString(target));

        // 冒泡排序要完成 ， N * (N - i - 1) 次循环 + swap 次数
    }
}
